In many digital systems, such as communications networks, user data and control traffic contend for processing time slots either within a system architecture or-at a system to system interface. In order to provide some control to the handling of such traffic it is common to generate one or more queues, typically in the form of first in first out (FIFO) buffers, wherein the traffic is separated in accordance with given traffic parameters and some form of arbitration is used to establish the order in which the queues are processed. Arbitration schemes such as round robin, exhaustive round robin or weighted round robin are commonly used.
In certain implementations, packets or cells, including both user data and control data are placed in queues for subsequent processing. If, however, the data packets or cells contain considerable information the data is placed in data buffers and the address assigned to each item in the data buffers is placed in the queues. Frequently, the items in the queues must be further processed either within the system or by an associated system having a separate processor.
The mechanisms for generating queues in software are generally well known. Typically, such queues are implemented as either an array such as a circular array or a linked list. Generally, queues make use of either an enqueue pointer or an index to identify where pointers to items or the items should be inserted into or added to the queue. Further, either a dequeue pointer or index to identify where pointers to items should be removed from the queue are provided. Optionally, a counter may be implemented that indicates the number of items or pointers to items currently stored on the queue.
Generally, the queues are of fixed size and before additional items may be added the queue size is checked to determine if there is room to insert another item. This is typically done by checking the optional counter described above or by calculating the difference between the enqueue pointer and the dequeue pointer.
A problem arises when there are multiple queues to be serviced and as discussed above, the items need to be processed by the system for some time after they have been removed from the queue. For a variety of reasons, i.e. division of responsibilities between processors for performance, access to memory systems in a multitask environment, interrupt handler, relatively complex algorithms for determining which queue to service next, etc., it is often desirable to have one task choose the next queue to remove an item from, remove the item and then pass it on to another processor, task, or procedure for subsequent processing.
Because the items are still being processed by the system after removal from the queue, the queue could be empty but a large number of items are still being consumed by the system. In order to prevent this situation from occurring, current implementations generally try to limit the rate at which items are removed from the queue so that items are dequeued at approximately the same rate at which they are subsequently processed.
This creates a difficult balance to achieve in practice and usually requires elaborate feedback mechanisms to instruct the processor responsible for dequeuing to either speed up or slow down.
A specific application requiring a mechanism for controlling queue size in a multiprocessor system relates to Newbridge Networks Corporation's Carrier Scale Internetworking (CSI) implementation. Carrier Scale Internetworking introduces the concept of Realms wherein a network is divided into virtual service networks which may encompass bridged or routed virtual private networks (VPN) or public internet connectivity. Through CSI a service provider can offer virtual private network services to individual customers. The service provider is also able to offer a differentiated class of service (CoS) through the CSI architecture. The Internetworking Service Card (ISC) within the CSI architecture provides, amongst other things, the class of service functionality. Currently, there are three classes of service offered, namely a control class for control traffic and standard and premium classes of service for user data traffic.
The ISC includes a multiprocessor environment wherein a first processor examines information packet headers and organizes the packets into separate queues according to the aforementioned criteria. The queues are serviced in accordance with an arbitration scheme and the items serviced from the queues are further processed in a second processor. As discussed previously, the task of controlling queue size in a multiprocessor environment presents a significant problem.
Accordingly, there is a requirement for an improved mechanism for controlling the queue length or queue size in a multi task processor system or a multiprocessor system in which items removed from queues continue to use up system resources during subsequent processing.